#include <iostream>
#include <time.h>
using namespace std;

//注意：本程序默认假币重量比真币小
int findCounterfeitCoin(double coins[], int low, int high);

int main()
{
	int n;
	cout << "请输入硬币个数：";
	cin >> n;
	double* coins = new double[n];
	double wm, wl;
	cout << "请输入硬币大多数重量和一枚假币重量：";
	cin >> wm >> wl;
	fill(coins, coins + n, wm);
	srand((unsigned)time(NULL));
	coins[rand() % n] = wl;
	cout << "硬币重量为：";
	for (int i = 0; i < n; i++)
	{
		cout << coins[i] << " ";
	}
	cout << endl;

	cout << "假币是第" << findCounterfeitCoin(coins, 0, n - 1) << "个" << endl;
	system("pause");
	return 0;
}

int findCounterfeitCoin(double coins[], int low, int high)
{
	int n = high - low + 1;
	//递归结束条件
	if (n == 1)
	{
		return low + 1;
	}

	// 分别存储3组硬币的个数
	int num1, num2, num3;
	//三分法
	if (n % 3 == 0)       //完全三分处理
	{
		num1 = num2 = n / 3;
	}
	else                 //非完全三分处理
	{
		num1 = num2 = n / 3 + 1;
	}
	num3 = n - num1 - num2;

	double add1 = 0.0, add2 = 0.0;
	for (int i = 0; i < num1; i++)                //计算第1组硬币的重量和
	{
		add1 += coins[low + i];
	}
	for (int i = num1; i < num1 + num2; i++)      //计算第2组硬币的重量和
	{
		add2 += coins[low + i];
	}

	if (add1 < add2)         //在第1组查找，下标范围是low~low+num1-1
	{
		return findCounterfeitCoin(coins, low, low + num1 - 1);
	}
	else if (add1 > add2)    //在第2组查找，下标范围low+num1~low+num1+num2-1
	{
		return findCounterfeitCoin(coins, low + num1, low + num1 + num2 - 1);
	}
	else                     //在第3组查找，下标范围low+num1+num2~high
	{
		findCounterfeitCoin(coins, low + num1 + num2, high);
	}
}
